package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.junit.Test;

public class Q425 {

    /**
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    public List<String> letterCombinations(String digits) {
        // write your code here
    	List<String> rs = new ArrayList<>();
    	if(digits ==  null || digits.length() == 0){
    		return rs;
    	}
    	Map<Character, String> map = new HashMap<>();
    	map.put('2', "abc");
    	map.put('3', "def");
    	map.put('4', "ghi");
    	map.put('5', "jkl");
    	map.put('6', "mno");
    	map.put('7', "pqrs");
    	map.put('8', "tuv");
    	map.put('9', "wxyz");
    	for(int i = 0; i < digits.length(); i ++){
    		char c = digits.charAt(i);
    		String s = map.get(c);
    		if (s == null){
    			return rs;
    		}
    		List<String> tmp1 = new ArrayList<>(rs);
    		List<String> rs1 = new ArrayList<>();
    		for(int j = 0;j< s.length(); j++){
    			char cc = s.charAt(j);
    			List<String> tmp2 = new ArrayList<>();
    			if(tmp1.size() == 0){
    				tmp2.add(String.valueOf(cc));
    			}else{
    				for(String ss : tmp1){
        				tmp2.add(ss + cc);
        			}
    			}
    			rs1.addAll(tmp2);
    		}
    		rs = rs1;
    	}
    	return rs;
    }

    @Test
    public void testLetterCombinations(){
    	System.out.println(letterCombinations("22"));
    }
}
